package cn.fxzhang.leetcode.no00;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 输入：s = "babad"
 * 输出："bab"
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 *
 * 类型：枚举/字符串处理
 * 题解：以1个字符串为中心，向两边扩展
 * 时间复杂度：O(N^2),
 * 空间复杂度：O(1)
 *
 * 提交记录(1/1)：
 * 执行用时: 42 ms, 击败了70.09%
 * 内存消耗: 39.1 MB, 击败了54.48%
 *
 * 【中等】通过次数534,253提交次数1,582,931
 * todo O(n)的解法
 * @author 张晓帆
 * @date 2021/4/2
 */
public class P0005_Longest_Palindromic_Substring {

    public String longestPalindrome(String s) {
        String ans = "";
        for (int i=0; i<s.length(); i++){
            String s1 = palindromic(s, i-1, i+1);
            String s2 = palindromic(s, i, i+1);
            if (s1.length() > ans.length()){
                ans = s1;
            }
            if (s2.length() > ans.length()){
                ans = s2;
            }
        }
        return ans;
    }

    private String palindromic(String s, int l, int r) {
        if (l<0 || r>=s.length()){
            return s.substring(0, 1);
        }
        while (l>=0 && r<s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l+1, r);
    }
}
